#include<assert.h>
#include<functional>
#include<string>
#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

template<class T, class Compare = less<T>>
class HeapGreater
{
public:
	HeapGreater()
	{}
	//迭代器初始化,用于利用迭代器往堆中插入元素
	template<class InputIterator>
	HeapGreater(InputIterator first, InputIterator last)
  {
    while(first != last)
    {
      push(*first);
      first++;
    }
  }
	~HeapGreater()
  {
    heap.clear();
    heapSize = 0;
  }

	void push(const T& x)
  {
    heap.push_back(x); 
    indexMap[x] = heapSize;
    AdjustUp(heapSize);
    heapSize++;
  }
	void pop()
  {
    assert(!empty());
    T& tmp = heap[0];
    swap(0,heapSize-1);//传入下标=>更改值&映射表
    heapSize--;
    heap.pop_back();
    indexMap.erase(tmp);
    AdjustDown(0); 
  }

	//更改obj元素的值为target
	void set(const T& obj,const T& target)
  {
    int index =  indexMap[obj];
    heap[index] = target;
    indexMap.erase(obj);
    indexMap[target] = index;
    resign(target);
  }
	//删除堆中指定的值
	void erase(const T& obj) 
  {
    int index = indexMap[obj];
    T& tail = heap[heap.size()-1];
    indexMap.erase(obj);
    heapSize--;
    if(obj != tail)
    {
      heap[index] = tail;
      indexMap[tail] = index;
      resign(tail);
    }
    heap.pop_back();
  }
	
  const T& top()
  {
    assert(!empty());
    return heap[0];
  }

	size_t size()
  {
    return heap.size();
  }

	bool empty()
  {
    return heap.empty();
  }

private:
	//需要封装交换函数,因为交换父亲和孩子的值的时候,indexMap中的值也需要交换
	void swap(int i, int j) //i和j是下标
  {
    T t1 = heap[i];
    T t2 = heap[j];

    heap[j] = t1;
    heap[i] = t2;
    
    indexMap[t1] = j;
    indexMap[t2] = i;
  }
	//向上调整算法,每push一个数都要调用向上调整算法,保证插入后仍是一个堆
	void AdjustUp(int child)
  {
    int parent = (child - 1 ) / 2;
    while(parent >= 0)
    {
      if(com(heap[child],heap[parent]))
      {
        swap(parent,child);
        child = parent;
        parent = (child - 1 ) / 2;
      }
      else 
      {
        break;
      }
    }
  }
	//向下调整算法,每次调用pop都要进行向下调整算法重新构成堆
	void AdjustDown(int parent)
  {
    int child = parent*2+1;
    int n = heap.size();
    while(child < n)
    {
      if(child + 1<n && com(heap[child+1],heap[child]))
        child += 1;

      if(com(heap[child],heap[parent]))
      {
        swap(child,parent);
        parent = child;
        child = parent*2+1;
      }
      else 
      {
        break;
      }
    }
  }
	//更改某个对象的值,堆结构发生变化,我们需要保持堆结构
	void resign(const T& obj)
  {
    int index = indexMap[obj];
    AdjustUp(index);
    AdjustDown(index);
  }

private:
  Compare com;
	vector<T> heap;//堆
	unordered_map<T, int>indexMap;	//反向索引表,记录一个元素在数组中的什么位置,不能使用map,因为key是元素值,如果key相同,不允许冗余
	int heapSize = 0 ;//堆的元素个数 =>注意:要给缺省值||构造函数当中进行赋值，否则其值是随机值影响后续的操作
};

void test_HeapGreater1()
{
	HeapGreater<string, less<string>> heap;
	heap.push("a");
	heap.push("c");
	heap.push("b");
	heap.push("d");
	heap.push("e");
	heap.push("z");
	heap.push("x");

	heap.erase("e");
	heap.set("c", "new c");
	while (!heap.empty())
	{
		cout << heap.top() << endl;
		heap.pop();
	}
}
struct cmp
{
	//比较的对象是string*类型对象
	bool operator()(string*& l, string*& r)
	{
		return *l < *r;//比较string对象,根据ascii比较
	}
};
void test_HeapGreater2()
{
	string* s1 = new string("a");
	string* s2 = new string("c");
	string* s3 = new string("b");
	string* s4 = new string("d");
	string* s5 = new string("e");
	string* s6 = new string("e");
	string* s7 = new string("z");
	string* s8 = new string("new c");

	HeapGreater<string*, cmp> heap;
	heap.push(s1);
	heap.push(s2);
	heap.push(s3);
	heap.push(s4);
	heap.push(s5);
	heap.push(s6);
	heap.push(s7);

	heap.erase(s5);
	heap.set(s2, s8);
	while (!heap.empty())
	{
		cout << *heap.top() << endl;
		heap.pop();
	}
}
void test_HeapGreater3()
{
	vector<string>v = { "a" ,"c" ,"b" ,"d" ,"e" ,"x" ,"z" };
	HeapGreater<string, less<string>> heap(v.begin(), v.end());

	heap.erase("e");
	heap.set("c", "new c");
	while (!heap.empty())
	{

		cout << heap.top() << endl;
		heap.pop();
	}
}
